package datastructure;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

/**
 * O(n^(2-p))-O(n^p*log(n)), usually set p to 0.5 thus O(n^1.5)-O(n^0.5*log(n))
 * p is sub-array length coefficient (length = n^p)
 * 
 * online algorithm for finding the value which appears most frequently in the
 * specific range
 * 
 * @author yinzichen
 * 
 */
public class RangeMaxCount {
	static int n, s, len;
	static int[] a;
	static int[][] maxCount;
	static int[][] maxValue;
	static HashMap<Integer, ArrayList<Integer>> val2Idx;
	static final double p = 0.4;

	public static void init(int[] array) {
		a = array;
		n = a.length;
		val2Idx = new HashMap<Integer, ArrayList<Integer>>();
		for (int i = 0; i < n; ++i) {
			if (!val2Idx.containsKey(a[i])) {
				val2Idx.put(a[i], new ArrayList<Integer>());
			}
			val2Idx.get(a[i]).add(i);
		}
		len = (int) Math.pow(n, p);
		s = (n + len - 1) / len;
		maxCount = new int[s][s];
		maxValue = new int[s][s];
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < s; ++i) {
			for (int j = i; j < s; ++j) {
				if (j > i) {
					maxCount[i][j] = maxCount[i][j - 1];
					maxValue[i][j] = maxValue[i][j - 1];
				}
				for (int k = j * len; k < Math.min((j + 1) * len, n); k++) {
					Integer val = map.get(a[k]);
					if (val == null) {
						val = 0;
					}
					map.put(a[k], val + 1);
					if (maxCount[i][j] < val + 1) {
						maxCount[i][j] = val + 1;
						maxValue[i][j] = a[k];
					}
				}
			}
			map.clear();
		}
	}

	static void rangeMaxCount(int l, int r) {
		int max = 0, val = -1;
		int i = (l + len - 1) / len, j = (r + 1) / len - 1;
		if (j >= i) {
			max = maxCount[i][j];
			val = maxValue[i][j];
		}
		int ll = l, rr = r;
		for (; ll <= Math.min(i * len - 1, rr); ll++) {
			ArrayList<Integer> idxList = val2Idx.get(a[ll]);
			int cnt = find(idxList, r + 1) - find(idxList, l);
			if (max < cnt) {
				max = cnt;
				val = a[ll];
			}
		}
		for (; rr >= Math.max((j + 1) * len, ll); --rr) {
			ArrayList<Integer> idxList = val2Idx.get(a[rr]);
			int cnt = find(idxList, r + 1) - find(idxList, l);
			if (max < cnt) {
				max = cnt;
				val = a[rr];
			}
		}
		System.out.println("value: " + val + " count: " + max);
	}

	static int find(ArrayList<Integer> idxList, int val) {
		int l = 0, r = idxList.size() - 1, m;
		while (l <= r) {
			m = l + r >> 1;
			if (idxList.get(m) >= val) {
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return r;
	}

	public static void main(String[] args) {
		int[] a = new int[] { 2, 3, 5, 6, 7, 3, 3, 4, 5, 6, 7, 9, 8, 7, 6, 5, 1 };
		init(a);
		Random ran = new Random(0);
		for (int i = 0; i < 10; ++i) {
			int l = ran.nextInt(n), r = ran.nextInt(n - l) + l;
			rangeMaxCount(l, r);
		}
	}

}
